package first_practice;

/**
 * @author ZhiWen Ren
 * @version 1.0
 * @description: LeetCode-124-二叉树中的最大路径和
 * @date 2025/4/19 14:36
 */
public class Solution124 {
    private int maxSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }

    public int maxGain(TreeNode root) {
        if (root == null)
            return 0;

        // 首先去找叶子节点的最大贡献值，小于0的话，就不走这条路径
        int leftTreePath = Math.max(maxGain(root.left), 0);
        int rightTreePath = Math.max(maxGain(root.right), 0);

        // 每次递归的时候，顺便更新最大路径值
        int tempMaxSum = root.val + leftTreePath + rightTreePath;

        maxSum = Math.max(maxSum, tempMaxSum);

        return root.val + Math.max(leftTreePath, rightTreePath);
    }
}
